package backtracking

import (
	"fmt"
)

// n=60,k=50,求1-n的排列中,有k个元素的排列,不能重复
// combine 排列组合
func combine(n int, k int) [][]int {
	var res [][]int
	var backtrack func(start int, path []int)
	backtrack = func(start int, path []int) {
		if len(path) == k {
			tmp := make([]int, k)
			copy(tmp, path)
			res = append(res, tmp)
			return
		}
		for i := start; i <= n; i++ {
			path = append(path, i)
			backtrack(i+1, path)
			path = path[:len(path)-1]
		}
	}
	backtrack(1, []int{})
	return res
}

func combineI(n int, k int) [][]int {
	var res [][]int
	var backtrack func(start int, path []int)
	backtrack = func(start int, path []int) {
		if len(path) == k {
			temp := make([]int, k)
			copy(temp, path)
			res = append(res, temp)
			return
		}
		for i := start; i <= n; i++ {
			path = append(path, i)
			backtrack(i+1, path)
			path = path[:len(path)-1]
		}
	}
	backtrack(1, []int{})
	return res
}

func getPackSlice() []int {
	// 一个背包总重量为w kg,n个物品重量各不相同，使用回溯算法求最接近承重极限的物品集合
	var maxW = -1                     // 结果放到maxW中
	var weight = []int{2, 2, 4, 6, 2} // 物品重量
	var n = 5                         // 物品个数
	var w = 9                         // 背包承受的最大重量

	var item []int      // 用于保存最优解
	var bestItems []int // 用于保存最优解
	var f func(i int, cw int)
	f = func(i int, cw int) { // 调用f(0, 0)
		if cw == w || i == n { // cw==w表示装满了，i==n表示物品都考察完了
			if cw > maxW {
				maxW = cw
				bestItems = make([]int, len(item))
				copy(bestItems, item)
				fmt.Println("maxW:", maxW, "item:", bestItems)
			}
			return
		}
		f(i+1, cw) // 选择不装第i个物品
		if cw+weight[i] <= w {
			item = append(item, weight[i]) // 选择装第i个物品
			f(i+1, cw+weight[i])
			item = item[:len(item)-1] // 回溯
		}
	}
	f(0, 0)
	return bestItems
}

func getPackSliceI() []int {
	var maxW = -1
	var weight = []int{2, 4, 6, 2, 4}
	var n = 5
	var w = 9
	var item []int
	var bestItem []int
	var f func(i int, cw int)
	f = func(i, cw int) {
		if cw == w || i == n {
			if cw > maxW {
				maxW = cw
				bestItem = make([]int, 0)
				copy(bestItem, item)
			}
			return
		}
		f(i+1, cw) // 不装这个物品
		if cw+weight[i] <= w {
			item = append(item, weight[i])
			f(i+1, cw+weight[i])
			item = item[:len(item)-1] // 去掉现在的物品
		}
	}
	f(0, 0)
	return bestItem
}

func getPackSliceByPack() int {
	var wt = []int{2, 4, 6, 2, 4}
	var maxW = 9
	var n = 5
	var f func(w int, cW int, n int) int
	f = func(w, cW, n int) int {
		tempRes := 0
		if w == 0 || n == 0 {
			return tempRes
		}
		if wt[n-1] > w {
			f(w, cW, n-1)
		}
		if cW+wt[n-1] <= maxW {
			tempRes = max(wt[n-1]+f(w-wt[n-1], cW+wt[n-1], n-1), f(w, cW, n-1))
		}
		return tempRes
	}
	res := f(maxW, 0, n)
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
